package impl;

import anaydis.sort.SorterType;
import org.jetbrains.annotations.NotNull;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * Created by IntelliJ IDEA.
 * User: Graciela
 * Date: 20/10/11
 * Time: 11:11
 * To change this template use File | Settings | File Templates.
 */
public class QuickSorterThreeWay extends AbstractSorter {

    public QuickSorterThreeWay(){
        super(SorterType.QUICK_THREE_PARTITION);
    }

    boolean bienOrdenado;
    public boolean getBienOrdenado(){
        return bienOrdenado;
    }

    public <T> void sort(Comparator<T> tComparator, List<T> ts){
        List<Integer> pivotes = new ArrayList<Integer>();
        pivotes.add(0);
        pivotes.add(ts.size());
        int i = 0;
        int[] g = new int[2];
        while((i*2)+1<pivotes.size()){
            if((Math.abs(pivotes.get((2*i)+1) - pivotes.get(2*i)) > 2) && (((pivotes.get((2*i)+1))>1) || pivotes.get(2*i)>1)) {
                g = partition(tComparator, ts, pivotes.get(2*i) , pivotes.get((2*i)+1), (pivotes.get((2*i)+1))-1);
             pivotes.add(pivotes.get(2*i));
             pivotes.add(g[0]);
             pivotes.add(g[1]);
             pivotes.add(pivotes.get((2*i)+1));
            }else{
                if(greater(tComparator, ts, 0, 1)){
                    swap(ts, 0, 1);
                }
                if(greater(tComparator, ts, 1, 2)){
                    swap(ts, 1, 2);
                }
            }
        i++;
        }
        //chequeos
        bienOrdenado = true;
        for(int w = 0; w<ts.size()-1;w++){
            if(greater(tComparator, ts, w, w+1)){
                bienOrdenado = false;
            }
        }
        System.out.println(bienOrdenado);

    }

/*partition ubica el pivote en su posicion final, y a todos los mayores
*a el a la derecha y los menores o iguales a izquierda.
*Return indice final del pivote
*/

protected <T> int[] partition(Comparator<T> tComparator, List<T> ts,int desde, int hasta, int pivote){
    int i = desde;
    int j = hasta-2;
    int[] g = new int[2];
    int cant = 0;
    boolean end = false;
    swap(ts, pivote, hasta-1);
    pivote = hasta-1;
    do{
        boolean imayor = false;
        while((!imayor) && i<j+1 && j>1){                         //busca el primer elemento mayor al pivote
            if(greater(tComparator, ts, i,pivote)){
                imayor = true;
            }else{
                if(equals(tComparator, ts, i,pivote)){
                    cant++;
                    pivote--;
                    j--;
                    swap(ts, i, pivote);
                }else{
                    i++;
                }
            }
        }     // si i>=j+1, entonces los indices se cruzaron y "i" es la posicion final del pivote
            boolean jmenor = false;
            while((!jmenor) && i<j+1 && j>0){                         //busca el ultimo elemento menor al pivote
                if(!(greater(tComparator, ts, j,pivote))){
                    if(equals(tComparator, ts, j, pivote)){
                        cant++;
                        pivote--;
                        swap(ts, j, pivote);
                        if(j == pivote){
                            j--;
                        }
                    }else{
                        jmenor = true;
                    }
                }else{
                    j--;
                }
            }
            if(i<j){                    //si los indices no se cruzaron todavia, intercambia los elementos
                swap(ts, i, j);
            }
            else{                       //si ya se cruzaron, ubica el pivote en su nueva posicion
                for(int u = 0; u<cant+1;u++){
                    swap(ts,i+u,pivote+u);
                }
                end = true;
            }
    }while(end==false);
    g[0] = i;
    g[1] = i + cant;


    //chequeos de funcionamiento
    System.out.println("Valor del pivote: "+ts.get(i));
    System.out.println("Posicion final pivote: "+i);
    System.out.println("Valor final de la primera parte: "+g[0]);
    System.out.println("Valor inicial de la segunda parte: "+g[1]);
    System.out.print("OrdenParcial: ");
    for(int asd = 0; asd<ts.size(); asd++){
        System.out.print(" "+ts.get(asd));
    }
    System.out.println();


    return g;
    }

    @NotNull
    public SorterType getType(){
        return SorterType.QUICK_THREE_PARTITION;
    }
}
